package weekone;

public class ReverseKGroupLinkedList_25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        //分组，找到每一组的开始和结尾，按组遍历
        ListNode project = new ListNode(0, head);
        ListNode last = project;
        ListNode nextGroupHead = null;
        while (head != null) {
            ListNode end = getEnd(head, k);
            if (end == null) {
                break;
            }
            nextGroupHead = end.next;
            //处理head end之间的反转。
            reverseList(head, end);
            //反转之后，end是新的头, last的next指向end
            last.next = end;
            //新的结尾 head 指向下一组的head
            head.next = nextGroupHead;
            last = head;
            head = nextGroupHead;

        }
        return project.next;

    }

    private ListNode getEnd(ListNode head, int k) {
        while (head != null) {
            k--;
            if (k == 0) break;
            head = head.next;
        }
        return head;
    }


    private void reverseList(ListNode head, ListNode end) {
        //这里面的last是从head开始，会动head 到 end的节点数n-1条边。
        //1->2->3 变成 3->2->1,1的next会由分组边界处理。
        if (head == end) return;
        ListNode last = head;
        head = head.next;
        ListNode next = null;
        while (head != end) {
            next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        //最后要把end指向last
        end.next = last;
    }
}
